{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Binary Tree Right Side View"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: rightSideView"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二叉树的右视图"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个二叉树的 <strong>根节点</strong> <code>root</code>，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/02/14/tree.jpg\" style=\"width: 270px; \" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> [1,2,3,null,5,null,4]\n",
    "<strong>输出:</strong> [1,3,4]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> [1,null,3]\n",
    "<strong>输出:</strong> [1,3]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> []\n",
    "<strong>输出:</strong> []\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>二叉树的节点个数的范围是 <code>[0,100]</code></li>\n",
    "\t<li><meta charset=\"UTF-8\" /><code>-100 <= Node.val <= 100</code> </li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [binary-tree-right-side-view](https://leetcode.cn/problems/binary-tree-right-side-view/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [binary-tree-right-side-view](https://leetcode.cn/problems/binary-tree-right-side-view/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,null,5,null,4]', '[1,null,3]', '[]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "from queue import Queue\n",
    "class Solution:\n",
    "    def rightSideView(self, root):\n",
    "\n",
    "        dic = {}\n",
    "\n",
    "        queue = Queue()\n",
    "        queue.put((root, 0))\n",
    "        while not queue.empty():\n",
    "            node, depth = queue.get()\n",
    "            \n",
    "            if not node:\n",
    "                continue\n",
    "            if depth in dic:\n",
    "                dic[depth].append(node.val)\n",
    "            else:\n",
    "                dic[depth] = [node.val]\n",
    "\n",
    "            queue.put((node.left, depth + 1))\n",
    "            queue.put((node.right, depth + 1))\n",
    "\n",
    "        result = []\n",
    "        i = 0\n",
    "        while i in dic:\n",
    "            print(i)\n",
    "            result.append(dic[i][-1])\n",
    "            i += 1\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def rightSideView(self, root: 'TreeNode') -> 'List[int]':\n",
    "        ret, queue = [], []\n",
    "        if root:\n",
    "            queue.append((root, 0))\n",
    "        while queue:\n",
    "            node, depth = queue.pop(0)\n",
    "            \n",
    "            if node.left:\n",
    "                queue.append((node.left, depth + 1))\n",
    "            if node.right:\n",
    "                queue.append((node.right, depth + 1))\n",
    "            \n",
    "            if not queue or queue[0][1] > depth:\n",
    "                ret.append(node.val)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "from queue import Queue \n",
    "q = Queue() #创建队列对象\n",
    "class Solution:\n",
    "    def rightSideView(self, root: 'TreeNode') -> 'List[int]':\n",
    "        if root is None:return []\n",
    "        q = Queue() \n",
    "        q.put(root)\n",
    "        res = []\n",
    "        while not q.empty():\n",
    "            lenth = q.qsize()\n",
    "            for i in range(lenth):\n",
    "                node = q.get()\n",
    "                if node.right :\n",
    "                    q.put(node.right)\n",
    "                if node.left :\n",
    "                    q.put(node.left)\n",
    "                if i ==0 :\n",
    "                    res.append(node.val)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "#     def rightSideView(self, root):\n",
    "#         result = []\n",
    "#         if not root:\n",
    "#             return result\n",
    "#         queue = collections.deque()\n",
    "#         queue.append(root)\n",
    "\n",
    "#         while queue:\n",
    "#             n = len(queue)\n",
    "#             for i in range(n):\n",
    "#                 node = queue.popleft()\n",
    "#                 if i == n - 1:\n",
    "#                     result.append(node.val)\n",
    "#                 if node.left:\n",
    "#                     queue.append(node.left)\n",
    "#                 if node.right:\n",
    "#                     queue.append(node.right)\n",
    "#         return result\n",
    "\n",
    "    def rightSideView(self, root):#视频讲的方法是用pair，每次压入数据的时候，配上它的层，这样读取的时候就是动态刷新每层最后一个点\n",
    "        result = []\n",
    "        if not root:\n",
    "            return result\n",
    "        queue = collections.deque()\n",
    "        queue.append((root,0))\n",
    "\n",
    "        while queue:\n",
    "            n = len(queue)\n",
    "            for i in range(n):\n",
    "                node_tuple = queue.popleft()\n",
    "                if node_tuple[1] >= len(result):\n",
    "                    result.append(node_tuple[1])\n",
    "                result[node_tuple[1]] = node_tuple[0].val\n",
    "                if node_tuple[0].left:\n",
    "                    queue.append((node_tuple[0].left,node_tuple[1]+1))\n",
    "                if node_tuple[0].right:\n",
    "                    queue.append((node_tuple[0].right,node_tuple[1]+1))\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def rightSideView(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        if root == None:\n",
    "            return []\n",
    "        from collections import deque\n",
    "        que = deque()\n",
    "        que.append((root,1))\n",
    "        k = 1\n",
    "        res = []\n",
    "        tmp = None\n",
    "        while len(que):\n",
    "            a,b = que.popleft()\n",
    "            if b != k:\n",
    "                res.append(tmp)\n",
    "                k = b\n",
    "            tmp = a.val\n",
    "            if a.left:\n",
    "                que.append((a.left,b+1))\n",
    "            if a.right:\n",
    "                que.append((a.right,b+1))\n",
    "        res.append(tmp)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "#     def rightSideView(self, root):\n",
    "#         result = []\n",
    "#         if not root:\n",
    "#             return result\n",
    "#         queue = collections.deque()\n",
    "#         queue.append(root)\n",
    "\n",
    "#         while queue:\n",
    "#             n = len(queue)\n",
    "#             for i in range(n):\n",
    "#                 node = queue.popleft()\n",
    "#                 if i == n - 1:\n",
    "#                     result.append(node.val)\n",
    "#                 if node.left:\n",
    "#                     queue.append(node.left)\n",
    "#                 if node.right:\n",
    "#                     queue.append(node.right)\n",
    "#         return result\n",
    "\n",
    "    def rightSideView(self, root):#视频讲的方法是用pair，每次压入数据的时候，配上它的层，这样读取的时候就是动态刷新每层最后一个点\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        result = []\n",
    "        if not root:\n",
    "            return result\n",
    "        queue = collections.deque()\n",
    "        queue.append((root,0))\n",
    "\n",
    "        while queue:\n",
    "            n = len(queue)\n",
    "            print('size:',n)\n",
    "            for i in range(n):\n",
    "                node_tuple = queue.popleft()\n",
    "                if node_tuple[1] >= len(result):\n",
    "                    result.append(node_tuple[1])\n",
    "                result[node_tuple[1]] = node_tuple[0].val\n",
    "                print('node:',node_tuple[0].val)\n",
    "                if node_tuple[0].left:\n",
    "                    queue.append((node_tuple[0].left,node_tuple[1]+1))\n",
    "                if node_tuple[0].right:\n",
    "                    queue.append((node_tuple[0].right,node_tuple[1]+1))\n",
    "\n",
    "        print('result:',result)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        result = []\n",
    "\n",
    "        def helper(node, level):\n",
    "            if node == None:\n",
    "                return result\n",
    "            if len(result) > level:\n",
    "                result[level].append(node.val)\n",
    "            else:\n",
    "                result.append([node.val])\n",
    "\n",
    "            helper(node.left, level + 1)\n",
    "            helper(node.right, level + 1)\n",
    "\n",
    "        helper(root, 0)\n",
    "        result_ = []\n",
    "        for r in result:\n",
    "            result_.append(r[-1])\n",
    "        return result_\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        result = []\n",
    "        if not root:\n",
    "            return result\n",
    "\n",
    "        stack = [(root, 1)]\n",
    "        index = 0\n",
    "        while stack:\n",
    "            node, cur = stack.pop()\n",
    "            if cur > index:\n",
    "                result.append(node.val)\n",
    "                index += 1\n",
    "            if node.left:\n",
    "                stack.append((node.left, cur + 1))\n",
    "            if node.right:\n",
    "                stack.append((node.right, cur + 1))\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        max_depth = -1\n",
    "        right_view_dict = dict()\n",
    "        queue = collections.deque([(root, 0)])\n",
    "\n",
    "        while queue:\n",
    "            node, depth = queue.popleft()\n",
    "            if node:\n",
    "                # max_depth = max(depth, max_depth)\n",
    "                right_view_dict.setdefault(depth, node.val)\n",
    "                queue.appendleft((node.left, depth+1))\n",
    "                queue.appendleft((node.right, depth+1))\n",
    "        return [right_view_dict[depth] for depth in right_view_dict]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        if not root :return []\n",
    "        queue = [(1,root)];res = [root.val]\n",
    "        i = 0;cur_dpth = 1\n",
    "        while i <len(queue):    \n",
    "            dpth,node = queue[i]\n",
    "            if dpth > cur_dpth:\n",
    "                cur_dpth = dpth\n",
    "                res.append(node.val)\n",
    "            if node.right:\n",
    "                queue.append((dpth+1,node.right))\n",
    "            if node.left:\n",
    "                queue.append((dpth+1,node.left))\n",
    "            i += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "        queue = [root]\n",
    "        ans = []\n",
    "        while queue:\n",
    "            cnt = len(queue)\n",
    "            level = []\n",
    "            for i in range(cnt):\n",
    "                node = queue.pop(0)\n",
    "                if node.left:\n",
    "                    level.append(node.left)\n",
    "                if node.right:\n",
    "                    level.append(node.right)\n",
    "                if i == cnt - 1:\n",
    "                    ans.append(node.val)\n",
    "            queue = level\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        if root is None:\n",
    "            return []\n",
    "        curLayer=[root]\n",
    "        nextLayer=[]\n",
    "        ans=[]\n",
    "        while len(curLayer)>0:\n",
    "            for node in curLayer:\n",
    "                if node.left:\n",
    "                    nextLayer.append(node.left)\n",
    "                if node.right:\n",
    "                    nextLayer.append(node.right)\n",
    "            ans.append(curLayer[-1].val)\n",
    "            curLayer=nextLayer\n",
    "            nextLayer=[]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "        \n",
    "        ans = []\n",
    "        stack = [root]\n",
    "        while stack:\n",
    "            n = len(stack)\n",
    "            for i in range(n):\n",
    "                node = stack.pop(0)\n",
    "                if i == 0: \n",
    "                    ans.append(node.val)\n",
    "                if node.right:\n",
    "                    stack.append(node.right)\n",
    "                if node.left:\n",
    "                    stack.append(node.left)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        # bfs 层次遍历， 取每层最右端的元素\n",
    "        from collections import deque, defaultdict\n",
    "        if not root:\n",
    "            return []\n",
    "        dic = defaultdict(list)\n",
    "        q = deque()\n",
    "        q.append((1, root))\n",
    "        while q:\n",
    "            level, node = q.popleft()\n",
    "            dic[level].append(node.val)\n",
    "            if node.left:\n",
    "                q.append((level + 1, node.left))\n",
    "            if node.right:\n",
    "                q.append((level + 1, node.right))\n",
    "        return [i[-1] for i in dic.values()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        queue = [(root, 0)]\n",
    "        max_depth = -1\n",
    "        print_dict = {}\n",
    "        res = []\n",
    "\n",
    "        def bfs(node, depth):\n",
    "            nonlocal print_dict\n",
    "            nonlocal max_depth\n",
    "            if not node:\n",
    "                return \n",
    "            max_depth = max(depth, max_depth)\n",
    "            if depth not in print_dict:\n",
    "                print_dict[depth] = node.val\n",
    "            bfs(node.right, depth + 1)\n",
    "            bfs(node.left, depth + 1)\n",
    "        bfs(root, 0)\n",
    "\n",
    "        return [print_dict[i] for i in range(max_depth + 1)]\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        res = [0] * 1000\n",
    "        def dfs(root, depth):\n",
    "            if not root:\n",
    "                return\n",
    "            res[depth] = root.val\n",
    "            dfs(root.left, depth + 1)\n",
    "            dfs(root.right, depth + 1)\n",
    "        dfs(root, 0)\n",
    "        for i in range(len(res)):\n",
    "            if res[i] == 0:\n",
    "                break\n",
    "        return res[:i]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        res=[]\n",
    "        queue=[root]\n",
    "        if not root:\n",
    "            return []\n",
    "        while queue:\n",
    "            size=len(queue)\n",
    "            for i in range(size):\n",
    "                a=queue.pop(0)\n",
    "                if a.left:\n",
    "                    queue.append(a.left)\n",
    "                if a.right:\n",
    "                    queue.append(a.right)\n",
    "                if i==size-1:\n",
    "                    res.append(a.val)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        if root is None: return []\n",
    "        ans = []\n",
    "        nodes = [root]\n",
    "        while nodes:\n",
    "            ans.append(nodes[-1].val)\n",
    "            tmp = []\n",
    "            for n in nodes:\n",
    "                if n.left:\n",
    "                    tmp.append(n.left)\n",
    "                if n.right:\n",
    "                    tmp.append(n.right)\n",
    "            nodes = tmp\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque \n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        dq = deque([root])\n",
    "        all_ceng = []\n",
    "\n",
    "        while len(dq)!=0:\n",
    "            rows = []\n",
    "            for _ in range(len(dq)):\n",
    "                node = dq.pop()\n",
    "                if node:\n",
    "                    rows.append(node.val)\n",
    "                    dq.appendleft(node.left)\n",
    "                    dq.appendleft(node.right)\n",
    "            if rows:\n",
    "                all_ceng.append(rows)\n",
    "            # print(rows)\n",
    "\n",
    "        return [rows[-1] for rows in all_ceng]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        ans=[]\n",
    "        res=[]\n",
    "        def dfs(root,depth):\n",
    "            if not root:return\n",
    "            if len(res)==depth:\n",
    "                res.append([])\n",
    "            res[depth].append(root.val)\n",
    "            dfs(root.left,depth+1)\n",
    "            dfs(root.right,depth+1)\n",
    "        dfs(root,0)\n",
    "        for i in range(len(res)):\n",
    "            ans.append(res[i][-1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        def helper(root, d):\n",
    "            if not root: return\n",
    "            if d >= len(res):\n",
    "                res.append(root.val)\n",
    "            else:\n",
    "                res[d] = root.val\n",
    "            helper(root.left, d+1)\n",
    "            helper(root.right, d+1)\n",
    "        res = []\n",
    "        helper(root, 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "import copy\n",
    "from typing import *\n",
    "class Solution:\n",
    "    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        if root is None:\n",
    "            return []\n",
    "\n",
    "        bfsQueue = []\n",
    "        bfsQueue.append(root)\n",
    "        bfsResult = []\n",
    "        while bfsQueue:\n",
    "            curLevel = []\n",
    "            curLevelSize = len(bfsQueue)\n",
    "            for i in range(curLevelSize):\n",
    "                curNode = bfsQueue.pop(0)\n",
    "                curLevel.append(curNode)\n",
    "                if curNode.left is not None:\n",
    "                    bfsQueue.append(curNode.left)\n",
    "                if curNode.right is not None:\n",
    "                    bfsQueue.append(curNode.right)\n",
    "            bfsResult.append(copy.deepcopy(curLevel))\n",
    "        print(\"bfsResult:\", bfsResult)\n",
    "\n",
    "        ans = []\n",
    "        for level in bfsResult:\n",
    "            ans.append(level[-1].val)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "        queue=collections.deque([root])\n",
    "        result=[]\n",
    "\n",
    "        while queue:\n",
    "            level=[]\n",
    "            for i in range(len(queue)):\n",
    "                temp=queue.popleft()\n",
    "                level.append(temp.val)\n",
    "\n",
    "                if temp.right:\n",
    "                    queue.append(temp.right)\n",
    "                if temp.left:\n",
    "                    queue.append(temp.left)\n",
    "                \n",
    "            result.append(level[0])\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        ans=[]\n",
    "        def dfs(node:Optional[TreeNode],depth:int) -> None:\n",
    "            if node is None:\n",
    "                return\n",
    "            if depth==len(ans):\n",
    "                ans.append(node.val)\n",
    "            dfs(node.right,depth+1)\n",
    "            dfs(node.left,depth+1)\n",
    "        dfs(root,0)\n",
    "        return ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "        queue = [root]\n",
    "        temp = []\n",
    "        res = []\n",
    "        while queue:\n",
    "            res.append(queue[-1].val)\n",
    "            for node in queue:\n",
    "                if node.left:\n",
    "                    temp.append(node.left)\n",
    "                if node.right:\n",
    "                    temp.append(node.right)\n",
    "            queue = temp\n",
    "            temp = []\n",
    "        \n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
